package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
* 491.题目描述
* 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 递增子序列 {
    private Set<List<Integer>> result = new HashSet<>();
    /*
    * 深度优先搜索
    * 他这个子序列是不用连续的（注意）
    *  数组中的每个点都进行一次深搜----> 即该点作为序列的头元素
    * 深搜中，首先判断 当前元素相对于当前列表是否是递增的（列表一定是递增的）
    * 如果是，就将其加入列表，如果不是，返回
    * 若当前元素加入列表，就对当前元素的后续的所有元素进行深搜
    * */
    public static void main(String[] args) {
        递增子序列 demo = new 递增子序列();
        List<List<Integer>> result2 = demo.findSubsequences(new int[]{4,3,2,1});
        for(List<Integer> t:result2){
            System.out.println(t.toString());
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
       List<Integer> list = new ArrayList<>();
       for(int i=0;i<nums.length;i++){
           f(nums,i,list);
       }
       List<List<Integer>> result1 = new ArrayList<>(result);
        return result1;
    }
    public void f(int[] nums,int i,List<Integer> list){
        if(list.size()!=0&&list.get(list.size()-1)>nums[i]) {//不递增
            return;
        }

        //如果是递增的话，加入队列，同时判断下一个元素是否递增
        list.add(nums[i]);
        if(list.size()>=2){
            result.add(new ArrayList<>(list));
        }
        //判断下一个元素是否递增
        for(int j=i+1;j<nums.length;j++){
            f(nums,j,list);
        }
        list.remove((Object)nums[i]);
    }
}
